#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<set>
using namespace std;

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        set<pair<int,int>> S;
        for(int i = 0;i<board.size();++i){
            for(int j=0;j<board[i].size();++j){
                if(board[i][j] == word[0]){
                    bool result = DFS(board,word,i,j,0,S);
                    if(result){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    bool DFS(vector<vector<char>>& board,string word,int i,int j,int index,set<pair<int,int>> S){
        if(i<0||i>=board.size()||j<0||j>=board[0].size()||word[index]!=board[i][j]||S.find(make_pair(i,j))!=S.end()){
            return false;
        }
        if(index==word.size()-1&&word[index]==board[i][j]){
            return true;
        }
        S.insert(make_pair(i,j));

        bool result = ((DFS(board,word,i-1,j,index+1,S))||(DFS(board,word,i+1,j,index+1,S))||(DFS(board,word,i,j-1,index+1,S))||(DFS(board,word,i,j+1,index+1,S)));
        return result;

    }
};

int main(){
    vector<vector<char>> boards = {{'a','a','a','a'},{'a','a','a','a'},{'a','a','a','a'},{'a','a','a','a'},{'a','a','a','b'}};
    Solution S;
    cout<<S.exist(boards,"aaaaaaaaaaaaaaaaaaaa")<<endl;
    
}